Conventionally, a content addressable memory (CAM) device may include a priority encoder circuit. A conventional priority encoder circuit can typically receive a number of match results that correspond to CAM entries. Such match results can have an active level (indicating a match condition) and an inactive level (indicating a no match condition). A priority encoder circuit may encode a highest priority match result into an output value. Such an output value is typically a binary value that is often referred to as an index value.
Conventional priority encoders typically include a priority select circuit and an encoding circuit, such as a read-only-memory (ROM) type circuit. When multiple active match results are received, a priority selection circuit can select one of the active input signals according to predetermined criteria. For example, input signals may have a particular order, and a priority selection circuit may select a lowest active input signal of the particular order. It is noted that in some instances, a priority selection may also be referred to as a priority encoder.
An active prioritized match result provided by a conventional priority selection circuit can then be provided as an input to a ROM-type circuit. A ROM-type circuit may then generate an index value corresponding to the particular active match indication.
To better understand the structure and operation of conventional priority encoder circuits, and to better understand the various features of the disclosed embodiments, a number of conventional circuits will now be described.
Referring now to FIG. 7, a conventional CAM device that includes a conventional priority encoder circuit is set forth in block schematic diagram and designated by the general reference character 700. A CAM device 700 may include a number of CAM entries 702 and a priority encoder circuit 704. CAM entries 702 may include multiple CAM entries, each of which can store a data value for comparison with an applied comparand value (or key). Match results generated by CAM entries 702 are shown as M0 to Mn.
A priority encoder 704 may include a priority select circuit 706 and a ROM-type encoder circuit 708. A priority selection circuit 706 may provide prioritized signals P0 to Pn, each of which can correspond to match results M0 to Mn. Thus, signals P0 to Pn can be considered prioritized match results. Thus, assuming that a lowest match result has a highest priority value, if match indication M0, M3 and Mn were active, only a corresponding highest priority output signal P0 would be activated by priority selection circuit 706. That is, a conventional priority select circuit 706 can activate only one prioritized match result for a given search.
A ROM-type circuit 708 may receive output signals P0 to Pn as ROM word line signals RWL0 to RWLn. A different combination of index bit value signals ID0 to IDx may be activated for each different ROM word line (RWL0 to RWLn).
In many cases, a conventional CAM can be subject to various physical layout restrictions. Referring now to FIG. 8, a conventional CAM layout arrangement will be described. FIG. 8 is a top plan view of a CAM device that is designated by the general reference character 800. A CAM device 800 may include first CAM entries 802, second CAM entries 804, and a priority encoder circuit 806. A priority encoder circuit 806 may include a priority selection circuit 807 and a read-only-memory (ROM) encoding circuit 808.
First and second entries (802 and 804) may each include a number of CAM entries 810. CAM entries 810 may provide match results to a priority encoder circuit 806 by signal lines. Two examples of signal lines are shown as 812. A ROM encoding circuit 808 may include a number of ROM entries, each of which can encode a match result into an output value, such as an index value. A top ROM entry is shown as item 814, while a bottom ROM entry is shown as 816.
A priority encoder 806 and ROM encoding circuit 808 may be situated between first CAM entries 802 and second CAM entries 804. Thus, FIG. 8 shows a conventional CAM in which one entry can be situated on either side of a priority encoder 806 and ROM encoding circuit 808 (one entry from first CAM entries 802 on one side, and one entry from second CAM entries 804 on another side).
It is understood that in FIG. 8, circuit dimensions in a vertical direction can be considered proportional between a CAM entries 810 and ROM entries (e.g., 814 and 816). Thus, a measurement 818 can be considered a “height” for CAM entries 810, while a measurement 820 can be considered a “height” for a ROM row (e.g., 814 and 816). A CAM entry height 818 may be dictated by a CAM cell height. Thus, the conventional case of FIG. 8 shows an arrangement in which a CAM cell height can correspond to the height of two ROM entries (e.g., 814 and 816).
Referring now to FIG. 9, a schematic diagram of a portion of a conventional ROM encoding circuit according to one embodiment is set forth and designated by the general reference character 900. A conventional ROM 900 may include a number of ROM entries 902-0 to 902-7. Each ROM entry (902-0 to 902-7) may be connected to a ROM word line RWL0 to RWL7. As shown by FIG. 9, ROM word lines (RWL0 to RWL7) may correspond to prioritized match indications. Thus, in operation, no more than one ROM word line (RWL0 to RWL7) may be active at a time. Each ROM entry (902-0 to 902-7) can encode an activated ROM word line (RWL0 to RWL7) into an output value, a portion of which is shown as ID0 to ID2.
Referring to FIG. 10, a table is set forth showing a response of the conventional ROM encoder circuit shown in FIG. 9.
The above conventional examples have shown arrangements in which two ROM entries may fit within the height of one CAM cell (or a CAM entry height). However, as CAM device capacities are increased, it would be desirable to utilize a same general ROM encoder circuit area to serve a larger number of CAM cells.
One example of a priority encoder/ROM is disclosed in U.S. Pat. No. 6,268,807, issued to Miller et al., on Jul. 31, 2001.
In addition, or alternatively, it may be desirable to arrive at some way to accommodate more CAM entries for a given basic ROM type circuit design, without having to substantially redesign such a ROM type circuit. Such an approach may advantageously utilize existing ROM type circuit designs.